1925D - Good Trip - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef tree<pair<int, int>, null_type, greater<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define AboTaha_on_da_code ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define X first
#define Y second

const int dx[8]={0, 0, 1, -1, 1, -1, -1, 1};
const int dy[8]={1, -1, 0, 0, 1, -1, 1, -1};
const int mod = 1e9+7; // 1e9+7, 998244353
const double EPS = 1e-8;
// BEFORE coding are you sure you understood the statement correctly?
// PLEASE do not forget to read the sample explanation carefully.
// WATCH out for overflows & RTs in general.
// TEST your idea or code on the corner cases.
// ANALYZE each idea you have thoroughly.

int mpow(int a, int b, int m)
{
    int res = 1;
    while(b) {
        if (b&1) res = 1LL*res*a%m;
        a = 1LL*a*a%m, b/=2;
    }
    return res;
}

const int N = 2e5+10;
int fact[N], invfact[N];
void pre()
{
    fact[0] = invfact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = 1LL*fact[i-1]*i%mod;
        invfact[i] = mpow(fact[i], mod-2, mod);
    }
}

int nCr(int n, int r)
{
    if (r > n) return 0;
    return 1LL*fact[n]*invfact[r]%mod*invfact[n-r]%mod;
}

inline int inv(int x) {
    return mpow(x, mod-2, mod);
}

void burn(int tc) {
    int n, m, k; cin >> n >> m >> k;
    ll sm = 0;
    for (int i = 0; i < m; i++) {
        int x; cin >> x >> x >> x;
        sm+=x;
        if (sm >= mod) sm-=mod;
    }
    int ans = 0;
    for (int x = 0; x < k; x++) {
        int cur = 1LL*(x+1)*(2*sm+x)/2%mod*inv(m)%mod;
        cur = 1LL*cur*mpow(1LL*m*inv(nCr(n, 2))%mod, x+1, mod)%mod;
        cur = 1LL*cur*mpow((mod+1-1LL*m*inv(nCr(n, 2))%mod)%mod, k-x-1, mod)%mod;
        cur = 1LL*cur*nCr(k, x+1)%mod;
        ans+=cur;
        if (ans >= mod) ans-=mod;
    }
    cout << ans;
}

int main() {

    AboTaha_on_da_code

//    freopen("khoshaf.in", "r", stdin);
//    freopen("Aout.txt", "w", stdout);

    int _t = 1; cin >> _t;

    pre();

    for (int i = 1; i <= _t; i++) {
//        cout << "Case " << i << ": ";
        burn(i);
        cout << '\n';
    }
    return 0;
}